home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Tech Arsenal 1
/
Tech Arsenal (Arsenal Computer).ISO
/
tek-04
/
ad12.zip
/
TOPOSORT.AD
< prev
Wrap
Text File
|
1990-03-02
|
1KB
|
47 lines
┌ * Algorithm for topological sort
│
│ * Input: a set of ordered pairs that respresents a partial order.
│
│ * Output: a total order in which which the partial order is embedded.
│
│ * Data structures
│ * Assume a dictionary of items to be sorted.
│ * Must be able to store with each item the number of its
│ * predecessors and a pointer to a linked list of its
│ * successors in the partial order.
│
│ * Based on algorithm given in Data Structures and C Programs,
│ * C.J. Van Wyk
│
│ ┌ * Initialize data structures
│ │
│ │ ╔ For Each ordered pair (a, b) in the input
│ │ ║ Add 1 to b's count of predecessors
│ │ ║ Add b to a's list of successors
│ │ ╚ End For
│ │
│ │ Enqueue each item that has no predecessors
│ └
│
│ ┌ * Construct topological order
│ │
│ │ ╔ While the queue is not empty
│ │ ║
│ │ ║ ╔ For Each successor of the item at the head of the queue
│ │ ║ ║
│ │ ║ ║ Subtract 1 from its predecessor count
│ │ ║ ║
│ │ ║ ║ ╒ If its predecessor count is zero
│ │ ║ ║ │ Enqueue it
│ │ ║ ║ └ End If
│ │ ║ ║
│ │ ║ ╚ End For
│ │ ║
│ │ ║ Dequeue and output the item at the head of the queue
│ │ ║
│ │ ╚ End While
│ │
│ └
│
└